package com.fe.class09;


/**
 * @Description 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * 1）把链表放入数组里，在数组上做partition（笔试用）
 * 2）分成小、中、大三部分，再把各个部分之间串起来（面试用）
 * @Author sosuke :-)
 * @Date 2022/1/28 16:16
 */
public class Code03_LinkedListPartition {
    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 使用容器（数组）的方式实现
     * 链表依次放入数组，对数组进行划分（荷兰国旗问题，此方法不稳定），再将分区后对数组链接成链表
     *
     * @param head
     * @param pivot
     * @return 返回满足条件的链表头节点
     */
    public static Node partition01(Node head, int pivot) {
        // 节点数0、1，返回head
        if (head == null || head.next == null) {
            return head;
        }
        // 获取链表长度并初始化数组
        Node cur = head;
        int i = 0;
        while (cur != null) {
            i++;
            cur = cur.next;
        }
        Node[] nodeArr = new Node[i];
        cur = head;
        for (i = 0; i < nodeArr.length; i++) {
            nodeArr[i] = cur;
            cur = cur.next;
        }
        // 对数组进行分区
        arrPartition(nodeArr, pivot);
        // 将分区后的数组重新链接
        for (i = 1; i < nodeArr.length; i++) {
            nodeArr[i - 1].next = nodeArr[i];
        }
        nodeArr[nodeArr.length - 1].next = null; // 注意要把最后一个node.next设置为null
        return nodeArr[0];
    }

    // 对数组进行分区(这里数组长度>=2)，左中右
    private static void arrPartition(Node[] nodeArr, int pivot) {
        int windowL = -1;
        int windowR = nodeArr.length;
        int curIndex = 0;
        while (curIndex < windowR) {
            if (nodeArr[curIndex].value == pivot) {
                curIndex++;
            } else if (nodeArr[curIndex].value < pivot) {
                swap(nodeArr, curIndex++, ++windowL);
            } else {
                swap(nodeArr, curIndex, --windowR); //注意这里curIndex不++，换过来后要接着下一轮的判断
            }
        }
    }

    private static void swap(Node[] nodeArr, int a, int b) {
        Node tmp = nodeArr[a];
        nodeArr[a] = nodeArr[b];
        nodeArr[b] = tmp;
    }

    /**
     * 尾插法实现，仅使用有限几个变量
     * 此方法稳定
     * @param head
     * @param pivot
     * @return 返回满足条件的链表头节点
     */
    public static Node partition02(Node head, int pivot) {
        Node sH = null, sT = null; // small Head,small Tail
        Node eH = null, eT = null; // equal Head,equal Tail
        Node bH = null, bT = null; // big Head,big Tail
        Node next = null; // 用于保存下一个节点
        // 遍历链表，将其按照比较结果链接到对应的链表上
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sH == null) {
                    sH = head;
                } else {
                    sT.next = head;
                }
                sT = head;
            } else if (head.value == pivot) {
                if (eH == null) {
                    eH = head;
                } else {
                    eT.next = head;
                }
                eT = head;
            } else {
                if (bH == null) {
                    bH = head;
                } else {
                    bT.next = head;
                }
                bT = head;
            }
            head = next;
        }
        // 将三个链表首尾链接
        // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
        if (sT != null) { // 如果有小于区域
            sT.next = eH;
            eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
        }
        if (eT != null) { // 如果小于区域和等于区域不都为空
            eT.next = bH;
        }
        return sH != null ? sH : (eH != null ? eH : bH);
    }

    public static void main(String[] args) {
        // int testTime = 100000;
        int maxSize = 10;
        int maxValue = 100;
        Node head = generateRandomLinkedList(maxSize, maxValue);
        Node copyHead = copyNode(head);
        int pivot = (int) (Math.random() * (maxValue + 1));
        System.out.print("origin list===>");
        printLinkedList(head);
        System.out.println("pivot = " + pivot);

        Node r1 = partition01(head, pivot);
        System.out.print("partition01 result===>");
        printLinkedList(r1);
        System.out.println();

        System.out.print("copy list===>");
        printLinkedList(copyHead);
        Node r2 = partition02(copyHead, pivot);
        System.out.print("partition02 result===>");
        printLinkedList(r2);
    }

    /**
     * 判断两个单链表是否相等
     * @param head1
     * @param head2
     * @return
     */
    public static boolean nodeEqual(Node head1, Node head2) {
        Node p1 = head1;
        Node p2 = head2;
        while (p1 != null && p2 != null) {
            if (p1.value != p2.value) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1 == null && p2 == null;
    }

    public static Node copyNode(Node head) {
        if (head == null) return null;
        Node p1 = head;
        Node p2 = new Node(p1.value);
        Node cur = p2;
        while (p1.next != null) {
            cur.next = new Node(p1.next.value);
            cur = cur.next;
            p1 = p1.next;
        }
        return p2;
    }

    /**
     * 随机生成单链表
     *
     * @return
     */
    public static Node generateRandomLinkedList(int maxSize, int maxValue) {
        // [0,maxSize]
        int size = (int) (Math.random() * (maxSize + 5));
        if (size == 0) return null;
        Node head = new Node((int) (Math.random() * (maxValue + 1)));
        size--;
        Node pre = head;
        for (int i = 0; i < size; i++) {
            Node next = new Node((int) (Math.random() * (maxValue + 1)));
            pre.next = next;
            pre = next;
        }
        return head;
    }

    /**
     * 打印单链表
     *
     * @param head
     */
    public static void printLinkedList(Node head) {
        if (null == head) {
            System.out.println("\"null\"");
            return;
        }
        Node cur = head;
        while (null != cur) {
            System.out.print(cur.value + "--->");
            System.out.print(cur.next == null ? "null" : "");
            cur = cur.next;
        }
        System.out.println();
    }
}
